//
//  CountSmaller.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/11.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  315. 计算右侧小于当前元素的个数

import UIKit

/*
 315. 计算右侧小于当前元素的个数


 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

 示例:

 输入: [5,2,6,1]
 输出: [2,1,1,0]
 解释:
 5 的右侧有 2 个更小的元素 (2 和 1).
 2 的右侧仅有 1 个更小的元素 (1).
 6 的右侧有 1 个更小的元素 (1).
 1 的右侧有 0 个更小的元素.
 */

class CountSmaller: NSObject {
    
    //暴力解法
    func countSmaller(_ nums: [Int]) -> [Int] {
        
        var resultArr = [Int]()
        
        for index in 0 ..< nums.count {
            var resultEle = 0
            for eleIndex in index+1 ..< nums.count {
                if nums[eleIndex] < nums[index] {
                    resultEle +=  1
                }
            }
            resultArr.append(resultEle)
        }
        
        return resultArr
    }
    
    
    
    
    //二叉树解法
    func countSmaller2(_ nums: [Int]) -> [Int] {
        
        var resultArr = [Int]()
        
        
        return resultArr
    }
}
